//给定一个整数 n，返回 n! 结果尾数中零的数量。 
//
// 示例 1: 
//
// 输入: 3
//输出: 0
//解释: 3! = 6, 尾数中没有零。 
//
// 示例 2: 
//
// 输入: 5
//输出: 1
//解释: 5! = 120, 尾数中有 1 个零. 
//
// 说明: 你算法的时间复杂度应为 O(log n) 。 
// Related Topics 数学 
// 👍 352 👎 0

package leetcode.editor.cn;

import common.util.MyUtil;

/**
 * Java：阶乘后的零
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P172_FactorialTrailingZeroes {
    public static void main(String[] args) {
        Solution solution = new P172_FactorialTrailingZeroes().new Solution();
        MyUtil.print(solution.trailingZeroes(88));

    }

    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * n / 5 + n / 25 + n / 125 ...
     */
    class Solution {
        public int trailingZeroes(int n) {
            int num5 = 0;
            while (n > 0) {
                n /= 5;
                num5 += n;
            }
            return num5;
        }
    }
    ///**
    // * 直接计算1-n中有多少个5
    // */
    //class Solution {
    //    public int trailingZeroes(int n) {
    //        int num5 = 0;
    //        for (int i = 1; i <= n; i++) {
    //            int temp = i;
    //            while (temp > 0) {
    //                if (temp % 5 != 0) {
    //                    break;
    //                }
    //                num5++;
    //                temp /= 5;
    //            }
    //
    //        }
    //        return num5;
    //    }
    //}
    //leetcode submit region end(Prohibit modification and deletion)

}